<?php
/**
 * @author : lihui
 * @email  : lihui@mama.com
 * @time   : 2022/7/29 17:24
 * 自定义固定容量数组
 */

namespace Xxb\XxbPhpAlgo;

class FixedArray
{
    public $data;
    /**
     * 可以有两层含义：
     * 1. 数组装了几个元素
     * 2. 当数组索引
     */
    public $size;

    public function __construct($capacity = 10)
    {
        $this->data = new \SplFixedArray($capacity);
        $this->size = 0;
    }

    /**
     * 获取数组容量
     * @return int
     */
    public function getCapacity()
    {
        return $this->data->getSize();
    }

    /**
     * 获取数组添加了几个元素
     * @return int
     */
    public function getSize()
    {
        return $this->size;
    }

    /**
     * 判断数组是否为空
     * 返回true 表示数组没有添加元素
     * 返回false 表示数组有添加元素
     * @return bool
     */
    public function isEmpty()
    {
        return $this->size == 0;
    }

    /**
     * 任意位置添加元素
     *
     * @param $index
     * @param $value
     */
    public function add($index, $value)
    {
        if ($index < 0 || $index > $this->size) {
            throw new \RuntimeException('add error, illegal index!');
        }
        if ($this->size == $this->getCapacity()) {
            // 超过容量之后，进行2倍扩容
            $this->resize($this->getCapacity() * 2);
        }
        for ($i=$this->size - 1; $i>=$index; $i--) {
            $this->data[$i+1] = $this->data[$i];
        }
        $this->data[$index] = $value;
        $this->size++;
    }

    /**
     * 对数组进行扩容或者缩容
     * @param $capacity
     */
    private function resize($capacity)
    {
        if ($capacity <= 0) {
            throw new \RuntimeException('resize array error, capacity is elt 0.');
        }
        $temp = new \SplFixedArray($capacity);
        for ($i=0; $i<$this->size; $i++) {
            $temp[$i] = $this->data[$i];
        }
        $this->data = $temp;
    }

    /**
     * 在头部添加元素
     * @param $ele
     */
    public function addFirst($ele)
    {
        $this->add(0, $ele);
    }

    /**
     * 在尾部添加元素
     * @param $ele
     */
    public function addLast($ele)
    {
        $this->add($this->size, $ele);
    }

    /**
     * 获取某个位置元素
     * @param $index
     *
     * @return mixed
     */
    public function get($index)
    {
        if ($this->isEmpty()) {
            throw new \RuntimeException('array is empty!');
        }

        if ($index >= $this->size || $index < 0) {
            throw new \RuntimeException('invalid index!');
        }

        return $this->data[$index];
    }

    /**
     * 获取第一个元素
     * @return mixed
     */
    public function getFirst()
    {
        return $this->get(0);
    }

    /**
     * 获取最后一个元素
     * @return mixed
     */
    public function getLast()
    {
        return $this->get($this->size - 1);
    }

    /**
     * 设置某个位置元素
     * @param $index
     * @param $ele
     */
    public function set($index, $ele)
    {
        if ($index >= $this->size || $index < 0) {
            throw new \RuntimeException('invalid index!');
        }
        if ($this->isEmpty()) {
            throw new \RuntimeException('array is empty!');
        }
        $this->data[$index] = $ele;
    }

    /**
     * 设置第一个元素
     * @param $ele
     */
    public function setFirst($ele)
    {
        $this->set(0, $ele);
    }

    /**
     * 设置最后一个元素
     * @param $ele
     */
    public function setLast($ele)
    {
        $this->set($this->size - 1, $ele);
    }

    /**
     * 返回查找到元素的第一个位置
     * 没有查找到则返回-1
     * @param $ele
     *
     * @return int
     */
    public function find($ele)
    {
        for ($i=0; $i<$this->size; $i++) {
            if ($this->data[$i] == $ele) {
                return $i;
            }
        }
        return -1;
    }

    /**
     * 删除某个位置的元素
     * @param $index
     *
     * @return mixed
     */
    public function remove($index)
    {
        if ($this->isEmpty()) {
            throw new \RuntimeException('remove error: array is empty!');
        }

        if ($index >= $this->size || $index < 0) {
            throw new \RuntimeException('remove error: invalid index!');
        }

        $ele = $this->data[$index];
        // 被删除位置的后面元素都往前移动
        for ($i=$index+1; $i<$this->size; $i++) {
            $this->data[$i-1] = $this->data[$i];
        }
        $this->data[$this->size - 1] = null;
        $this->size--;

        /**
         * 由于扩容是2倍原容量，如果这里缩容按0.5倍原容量的话，可能会出现时间复杂度震荡，操作上就是频繁的添加或删除最后的元素
         * 所以这里缩容按0.25倍原容量进行
         */
        $capacity = floor($this->getCapacity() / 4);
        if ($this->size == $capacity && $capacity > 0) {
            $this->resize($capacity);
        }
        return $ele;
    }

    /**
     * 删除第一个元素
     * @return mixed
     */
    public function removeFirst()
    {
        return $this->remove(0);
    }

    /**
     * 删除最后一个元素
     */
    public function removeLast()
    {
        return $this->remove($this->size - 1);
    }

    /**
     * 删除某个元素
     * @param $ele
     */
    public function removeEle($ele)
    {
        $index = $this->find($ele);
        if ($index != -1) {
            $this->remove($index);
        }
    }

    /**
     * 是否包含某个元素
     * @param $ele
     *
     * @return bool
     */
    public function contain($ele)
    {
        for ($i=0; $i<$this->size; $i++) {
            if ($this->data[$i] == $ele) {
                return true;
            }
        }
        return false;
    }

    /**
     * 返回php数组
     * @return array
     */
    public function toArray()
    {
        return $this->data->toArray();
    }

    public function __toString()
    {
        $str = 'array: top [';
        for ($i=0; $i<$this->size; $i++) {
            $str .= $this->data[$i] . ',';
        }
        return rtrim($str, ',') . ']';
    }
}
